package com.zlk.algorithm.bit;

import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * @program: algorithm
 * @ClassName FindShowKMCount
 * @description:一个数组中有一种数出现K次，其他数都出现了M次， 已知M > 1，K < M，找到出现了K次的数 要求额外空间复杂度O(1)，时间复杂度O(N)
 * @author: slfang
 * @create: 2023-12-28 10:18
 * @Version 1.0
 **/
public class FindShowKMCount {

    @Test
    public void test(){
        int testTimes =10000;
        int maxVal=9;//次数限制
        int numRange = 100;//取值范围
        int kinds = 5;//数组值所有种类数

        for (int i = 0; i < testTimes; i++) {
            int a = (int) (Math.random() * maxVal) + 1; // a [1 ~ 9]
            int b = (int) (Math.random() * maxVal) + 1; // b [1 ~ 9]
            int k = Math.min(a, b);
            int m = Math.max(a, b);
            // k < m
            if (k == m) {
                m++;
            }
            int[] randomKMArr = getRandomKMArr( numRange, kinds,k,m);
            int test = forTest(randomKMArr, k, m);
            int find = FindShowKMCount(randomKMArr, k, m);
            if(test!=find){
                System.out.println("error");
                System.out.println(test);
                System.out.println(find);
                return;
            }
        }
        //getRandomKMArr(maxVal,numRange,kinds);

        System.out.println("success");
//        int[] arr = new int[]{2,2,3,3,1,1,1,3,4,4,4};
//        FindShowKMCount(arr,2,3);
    }

    /**
     * 随机一个数 出现K次 其他数出现M次  K<M
     *
     * @param maxVal
     * @param numRange
     * @param maxKinds
     * @param k
     * @param m
     * @return
     */
    private int[] getRandomKMArr(int numRange, int maxKinds, int k, int m) {//maxVal=9
        int realKNum = randomNumber(numRange); //随机k的值
        int realK = k;
        int numKinds = (int) (Math.random() * maxKinds) + 2;//保证有两个
        int[] arr = new int[realK + (numKinds - 1) * m];
        int index = 0;
        //赋值K
        for (; index < realK; index++) {
            arr[index] = realKNum;
        }
        numKinds--;

        HashSet<Integer> set = new HashSet<>();
        set.add(realKNum);
        while (numKinds != 0) {
            int curNum = 0;
            do {
                curNum = randomNumber(numRange);
            } while (set.contains(curNum));
            set.add(curNum);
            numKinds--;
            for (int i = 0; i < m; i++) {
                arr[index++] = curNum;
            }
        }

        //随机乱序
        for (int i = 0; i < arr.length; i++) {
            // i 位置的数，我想随机和j位置的数做交换
            int randomIndex = (int)(Math.random()*arr.length);//0 ~ N-1
            int tmp = arr[i];
            arr[i] = arr[randomIndex];
            arr[randomIndex] = tmp;
        }
        return arr;
    }

    // [-range, +range]
    public static int randomNumber(int range) {
        return (int) (Math.random() * (range + 1)) - (int) (Math.random() * (range + 1));
    }


    public int  FindShowKMCount(int[] arr,int k,int m){
        int length = arr.length;
        int[] temp = new int[32];
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < 32; j++) {
                temp[j]+= (arr[i]>>j)&1;
            }
        }

        int j=0;
        for (int i = 0; i < temp.length; i++) {
            if(temp[i]%m!=0){// k上存在1
                j |= 1<<i;
            }
        }
        //System.out.println(j);
        return j;
    }

    /**
     * 对数器
     * @return
     */
    public int forTest(int[] arr,int k,int m){
        HashMap<Integer,Integer> countMap =new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if(countMap.containsKey(arr[i])){
                countMap.put(arr[i],countMap.get(arr[i])+1);
            }else{
                countMap.put(arr[i],1);
            }
        }
        Set<Integer> integers = countMap.keySet();
        for (Integer integer : integers) {
            if(countMap.get(integer)==k){
                return integer;
            }
        }
        return -1;
    }









}
